<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>Trie_Tree</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">字典树</h1>
<h2 id="toc-1">Trie树可以保存一些字符串、值的对应关系。</h2>
<p>Trie的强大之处在于他的时间复杂度十分的低，插入和查询的时间复杂度都是O（k）的，k为key的长度，与Trie中保存了多少个元素无关。</p>
<p>Hash的话，查询的是O(1)的，计算的时候就是O(k)的了，而且还有hash的值相同导致碰撞的问题</p>
<p>而Trie树的缺点就是空间消耗很大。</p>
<p>Trie树可以用指针动态分配，本文用数组写。</p>
<p>Trie树，又称单词查找树或者键树，是一种树形结构，hash树的变形，典型应用就是用于统计和排序大量的字符串(不仅限于字符串) ，所以日常生活中的用途就是搜索引擎中使用较多，可以最大限度地减少无谓的字符串比较，效率比hash更好</p>
<p>Trie树就是一个典型的空间换时间的思路，利用字符串的公共前缀来降低查询时间的开销来到达提高效率的目的</p>
<h2 id="toc-2">基本性质</h2>
<p>1) 根节点不包含字符，除根节点以外每个节点只有一个字符.
1) <strong>从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串</strong>
1) 每个节点的所有子节点包含的字符串不相同.
1) 如果字符的种类为n种，那么每个节点的出度为n，(浪费了大量的时间)
1) 插入、查询的时间复杂度是O(n)的，n为字符串的长度。</p>
<h2 id="toc-3">基本思路</h2>
<h3 id="toc-4">插入</h3>
<p>对一个单词，从根开始，沿着单词的哥哥字母所对应的数的节点分支向下走，直到单词遍历完，将最后的节点<strong>标记</strong>为红色，表示已经插入Trie树中</p>
<h3 id="toc-5">查询</h3>
<p>同样的，从根开始按照单词的字母顺序向下遍历Trie树，一旦发现某个节点标记不存在或者单词遍历完最后的节点未标记为红色，那么就是说该单词不存在，反之存在。</p>
<h3 id="toc-6">字典树的数据结构</h3>
<p>利用串构建一个字典树，保存了公共前缀信息，可以降低查询的时间复杂度</p>
<h5 id="toc-7">一共有26个小写英文字母，26个大写英文字母(某高楼写的24个</h5>
<h4 id="toc-8">talk is cheap , show me the code !</h4>
<div class="highlight"><pre><span></span><span class="kt">int</span> <span class="n">trie</span><span class="p">[</span><span class="n">maxn</span><span class="p">][</span><span class="mi">30</span><span class="p">],</span><span class="n">flg</span><span class="p">[</span><span class="mi">110</span><span class="p">],</span><span class="n">cnt</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">;</span>
<span class="kt">char</span> <span class="n">str</span><span class="p">[</span><span class="mi">110</span><span class="p">],</span><span class="n">str1</span><span class="p">[</span><span class="mi">110</span><span class="p">];</span>
<span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="kt">char</span> <span class="o">*</span><span class="n">s</span><span class="p">){</span>
    <span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">p</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">len</span><span class="p">;</span><span class="o">++</span><span class="n">i</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">id</span><span class="o">=</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="sc">&#39;a&#39;</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">trie</span><span class="p">[</span><span class="n">p</span><span class="p">][</span><span class="n">id</span><span class="p">])</span> <span class="n">p</span><span class="o">=</span><span class="n">trie</span><span class="p">[</span><span class="n">p</span><span class="p">][</span><span class="n">id</span><span class="p">]</span><span class="o">=++</span><span class="n">cnt</span><span class="p">;</span>
        <span class="k">else</span> <span class="n">p</span><span class="o">=</span><span class="n">trie</span><span class="p">[</span><span class="n">p</span><span class="p">][</span><span class="n">id</span><span class="p">];</span>
        <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">flag</span><span class="p">[</span><span class="n">p</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">bool</span> <span class="nf">query</span><span class="p">(</span><span class="n">cahr</span> <span class="o">*</span><span class="n">s</span><span class="p">){</span>
    <span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">p</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">len</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">id</span><span class="o">=</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="sc">&#39;a&#39;</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">trie</span><span class="p">[</span><span class="n">p</span><span class="p">][</span><span class="n">id</span><span class="p">])</span> <span class="k">return</span> <span class="nb">false</span> <span class="p">;</span>
        <span class="k">else</span> <span class="n">p</span><span class="o">=</span><span class="n">trie</span><span class="p">[</span><span class="n">p</span><span class="p">][</span><span class="n">id</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="k">if</span><span class="p">(</span><span class="n">flag</span><span class="p">[</span><span class="n">p</span><span class="p">])</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
    <span class="k">return</span> <span class="nb">false</span> <span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>确实觉得很简单啊，也许需要一张图？</p>
<p><img src="https://i.loli.net/2017/10/13/59e02f79edf11.png" alt="asd"></p>
<p>分别给出了字符串：</p>
<p>afr</p>
<p>af</p>
<p>b</p>
<p>cp</p>
<hr>
<p>By：Wahacer</p>
<p>2017.10.13</p>
<p>11:14</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>